package myself.a009BinaryTree;

import java.util.Stack;

/**
 * @author 叶之越
 * Description 递归和迭代实现树的遍历
 * Date 2021/1/26
 * Time 15:44
 * Mail 739153436@qq.com
 */
public class TraverseTheTree {

    public static void pre(Node head) {
        if (head == null) {
            return;
        }
        System.out.print(head.value + ",");
        pre(head.left);
        pre(head.right);
    }

    public static void mid(Node head) {
        if (head == null) {
            return;
        }
        mid(head.left);
        System.out.print(head.value + ",");
        mid(head.right);
    }

    public static void aft(Node head) {
        if (head == null) {
            return;
        }
        aft(head.left);
        aft(head.right);
        System.out.print(head.value + ",");
    }

    public static void pre2(Node head) {
        if (head == null) {
            return;
        }

        Stack<Node> stack = new Stack<>();
        stack.add(head);
        // 头左右
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            System.out.print(cur.value + ",");
            // 这个模板可以模仿 头左右 或者 头右左 的方法栈结构，什么后出就先压什么，比如下面右节点是后面再打印的，就先压入栈
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
    }

    // ================ 下面是迭代实现递归 =====================

    // 左头右，这个和前序还有后序遍历都不太一样，需要额外的记忆练习
    public static void mid2(Node head) {
        if (head == null) {
            return;
        }

        Stack<Node> stack = new Stack<>();
        while (!stack.isEmpty() || head != null) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                head = stack.pop();
                System.out.print(head.value + ",");
                head = head.right;
            }
        }
    }

    public static void aft2(Node head) {
        if (head == null) {
            return;
        }

        Stack<Node> stack = new Stack<>();
        Stack<Node> printStack = new Stack<>();
        stack.add(head);
        while (!stack.isEmpty()) {
            // 头右左
            Node cur = stack.pop();
            printStack.push(cur);
            // 和迭代版本的先序遍历一样，这里栈stack的出栈顺序就是 头右左
            if (cur.left != null) {
                stack.push(cur.left);
                continue;
            }
            if (cur.right != null) {
                stack.push(cur.right);
            }
        }
        // 左右头
        // 由于上面的 头右左 的出栈结构，使得我们下面的栈是相反的顺序就是 头左右 的顺序结构
        while (!printStack.isEmpty()) {
            System.out.print(printStack.pop() + ",");
        }
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.left.right.left = new Node(6);

/*        head.right.left = new Node(6);
        head.right.right = new Node(7);*/

//        pre(head);
//        System.out.println("========");
        mid(head);
        System.out.println("========");
//        aft(head);
//        System.out.println("========");

    }

    public static class Node {
        public Node left;
        public Node right;
        public int value;

        public Node() {
        }

        public Node(int value) {
            this.value = value;
        }
    }
}

